package com.example.algorithm.dynamicprogramming;

import java.util.Arrays;

import java.lang.Math;

/**
 * 给你一个 互不相同 的整数数组，其中 locations[i] 表示第 i 个城市的位置。
 * 同时给你 start，finish 和 fuel分别表示出发城市、目的地城市和你初始拥有的汽油总量：
 *
 *  每一步中，如果你在城市 i ，你可以选择任意一个城市 j ，满足 j != i 且 0 <= j < locations.length ，并移动到城市 j 。
 *  从城市 i 移动到 j 消耗的汽油量为 |locations[i] - locations[j]|，|x| 表示 x 的绝对值。
 *  请注意， fuel 任何时刻都 不能 为负，且你 可以 经过任意城市超过一次（包括 start 和 finish ）。
 *  请你返回从 start 到 finish 所有可能路径的数目。
 *  由于答案可能很大， 请将它对 10^9 + 7 取余后返回。
 *
 *  示例 1：
 * 输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
 * 输出：4
 * 解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
 * 1 -> 3
 * 1 -> 2 -> 3
 * 1 -> 4 -> 3
 * 1 -> 4 -> 2 -> 3
 *
 *  示例 2：
 * 输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
 * 输出：5
 * 解释：以下为所有可能的路径：
 * 1 -> 0，使用汽油量为 fuel = 1
 * 1 -> 2 -> 0，使用汽油量为 fuel = 5
 * 1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
 * 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
 * 1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
 *
 *  示例 3：
 * 输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
 * 输出：0
 * 解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。
 */
public class Leetcode1575_CountRoutes {
    static class Solution {
        /**
         * 动态规划(迭代)
         * dp[i][j]表示总油耗为 i，到达目的城市为 j 的路径数
         * @param locations
         * @param start
         * @param finish
         * @param fuel
         * @return
         */
        public int countRoutes2(int[] locations, int start, int finish, int fuel) {
            int totalCity = locations.length, MOD =  (int) Math.pow(10, 9) + 7;
            int[][] dp = new int[fuel + 1][totalCity];
            dp[0][start] = 1;  // 起点位置不需要油耗(初始化状态)
            for (int i = 0; i <= fuel; i++)
                for (int j = 0; j < totalCity; j++) {
                    if (dp[i][j] > 0) {
                        for (int nextCity = 0; nextCity < totalCity; nextCity++)
                            if (j != nextCity) { // 不能选择当前城市作为下一个到达的城市
                                int cost = Math.abs(locations[nextCity] - locations[j]); // 计算到下一个城市所需的油耗
                                if (i + cost <= fuel) // 从当前城市到下一个城市总油耗不超过总油量，要更新状态
                                    dp[i + cost][nextCity] = (dp[i + cost][nextCity] + dp[i][j]) % MOD;

                            }
                        }
                }
            int res = 0;
            for (int i = 0; i <= fuel; i++)  // 汇总所有不超过总油量能到达finish的结果
                res = (res + dp[i][finish]) % MOD;
            return res;
        }

        /**
         * 记忆化搜索(递归)
         * f[curPos][rest] 表示当前位于 curPos 城市，剩余的汽油量为 rest 时，到达终点 finish 的可能的路径总数
         * @param locations
         * @param start
         * @param finish
         * @param fuel
         * @return
         */
        public int countRoutes1(int[] locations, int start, int finish, int fuel) {
            int[][] f = new int[locations.length][fuel + 1];
            int totalCity = locations.length, MOD = (int)Math.pow(10, 9) + 7;
            for (int[] row : f) {
                Arrays.fill(row, -1);
            }
            class Stub {
                public int dfs(int curPos, int rest) {
                    if (f[curPos][rest] != -1) return f[curPos][rest]; // 已经计算过，直接返回即可
                    f[curPos][rest] = 0;
                    // 从当前城市到 finish城市的油耗大于剩余的油耗，说明不可达
                    if (Math.abs(locations[curPos] - locations[finish]) > rest) return 0;
                    for (int nextCity = 0; nextCity < totalCity; nextCity++) { // 尝试到达下一个城市
                        if (nextCity != curPos) {
                            int cost;
                            if ((cost = Math.abs(locations[curPos] - locations[nextCity])) <= rest) {
                                f[curPos][rest] += dfs(nextCity, rest - cost);
                                f[curPos][rest] %= MOD;
                            }
                        }
                    }
                    if (curPos == finish) f[curPos][rest] = (f[curPos][rest] + 1) % MOD;
                    return f[curPos][rest];
                }
            }

            return new Stub().dfs(start, fuel);
        }

        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            return countRoutes2(locations, start, finish, fuel);
        }
    }

    public static void main(String[] args) {
        int[] locations = {4, 3, 1};
        int start = 1, finish = 0, fuel = 6;
        System.out.println(new Solution().countRoutes(locations, start, finish, fuel));
    }
}
